package link_list;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * 题目：反向打印链表
 * 例：2 -> 3 -> 4 => 4 -> 3 -> 2
 */
public class PrintReserveLinkList {
    public static void main(String[] args) {
        PrintReserveLinkList p = new PrintReserveLinkList();
        ArrayList<Integer> list = p.printListFromTailToHead1(ListNode.getDefault());
        ArrayList<Integer> list2 = p.printListFromTailToHead2(ListNode.getDefault());
        ArrayList<Integer> list3 = p.printLinkList(ListNode.getDefault());
        System.out.println(Arrays.toString(list.toArray()));
    }


    /**
     * 递归解法
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        ArrayList<Integer> ret = new ArrayList<>();
        System.out.println("invoke method");
        if (listNode != null) {
            System.out.println("next node- " + (listNode.next == null ? "null" : listNode.next.val));

            ret.addAll(printListFromTailToHead1(listNode.next));
            ret.add(listNode.val);
            System.out.println("add node- " + listNode.val);
        }
        return ret;
    }

    /**
     * 头插法构建逆序列表
     * listNode   memo  _listNode   head
     *  1 2 3      -        -        -1
     *   2 3      2 3       1       -1 1
     *    3        3       2 1     -1 2 1
     *    -        -      3 2 1   -1 3 2 1
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {

        ArrayList<Integer> list = new ArrayList<>();

        ListNode head = new ListNode(-1);

        while (listNode != null) {
            ListNode memo = listNode.next;
            listNode.next = head.next;
            head.next = listNode;
            listNode = memo;
        }

        head = head.next;

        while(head != null) {
            list.add(head.val);
            head = head.next;
        }

        return list;
    }

    /**
     * 使用堆栈的方法，先进后出
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printLinkList(ListNode listNode) {

        Stack<Integer> stack = new Stack<Integer>();

        while (listNode != null) {
            stack.add(listNode.val);
            listNode = listNode.next;
        }

        ArrayList<Integer> list = new ArrayList<>();

        while(!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }
}
